package pro.softzhang.algo.lc200;

import pro.softzhang.algo.flag.book.BOfferII;
import pro.softzhang.algo.flag.knowledge.KArray;

/**
 * https://leetcode.cn/problems/find-the-duplicate-number/description/
 */
@BOfferII(3)
@KArray
public class LC287_FindRepeatNumber {
    public static void main(String[] args) {

    }

    static
    class Solution {
        public int findRepeatNumber(int[] nums) {
            int i = 0;
            while (i < nums.length) {
                if (nums[i] == i) {
                    i++;
                    continue;
                }
                if (nums[nums[i]] == nums[i]) {
                    return nums[i];
                }
                int tmp = nums[i];
                nums[i] = nums[tmp];
                nums[tmp] = tmp;
            }
            return -1;
        }
    }
}
